#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/9 10:17
# @USER    : Shengji He
# @File    : TranslateNumToStr.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from collections import defaultdict


class Solution:
    def __init__(self):
        self.marked = list(chr(ord('a') + i) for i in range(26))

    def splitnum(self, numlist, prev):
        temp = defaultdict(list)
        temp[0] =self.marked[int(numlist[0])]
        temp[1] =self.marked[int(numlist[1])]
        if 9 < int(''.join(numlist)) < 26:
            temp[2] = self.marked[int(''.join(numlist))]
        else:
            temp[2] = None
        output = {0: [], 1: []}

        for i in prev[0]:
            output[0].append(i + temp[0])
            if temp[2]:
                output[1].append(i + temp[2])
            else:
                output[1].append(i + temp[0] + temp[1])
        for i in prev[1]:
            if (i + temp[1]) not in output[1]:
                output[1].append(i + temp[1])
            if i not in output[0]:
                output[0].append(i)

        return output


    def translateNum(self, num: int) -> int:
        """
        给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
        一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

        示例 1:

            输入: 12258

            输出: 5

            解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

        提示：

        0 <= num < 231

        :param num: int
        :return: int
        """
        # numlist = list(str(num))
        # prev = defaultdict(list)
        # prev[1] = [self.marked[int(numlist[0])]]
        # prev[0] = ['']
        # for i in range(len(numlist) - 1):
        #     prev = self.splitnum(numlist[i: i + 2], prev)
        # for i in prev[0]:
        #     if i + self.marked[int(numlist[-1])] not in prev[1]:
        #         prev[1].append(i + self.marked[int(numlist[-1])])
        #
        # return len(prev[1])

        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            a, b = (a + b if "10" <= s[i - 2:i] <= "25" else a), a
        return a



if __name__ == '__main__':
    S = Solution()
    # num = 18822
    num = 24678124
    # num = 12258
    print(S.translateNum(num))
    print('done')
